package leetcode.code1091;

import java.util.LinkedList;
import java.util.Queue;

public class Solution extends Solution1091 {

	private int x;
	private int y;

	@Override
	public int shortestPathBinaryMatrix(int[][] grid) {
		if (grid == null || grid[0][0] == 1)
			return -1;
		x = grid.length;
		y = grid[0].length;
		if (grid[x - 1][y - 1] == 1)
			return -1;
		grid[0][0] = 1;
		Queue<int[]> s = new LinkedList<>();
		s.add(new int[] { 0, 0 });
		while (s.size() > 0) {
			int size = s.size();
			while (size > 0) {
				int[] now = s.poll();
				int a = now[0];
				int b = now[1];
				int next = grid[a][b] + 1;
				this.update(grid, a + 1, b, next, s);
				this.update(grid, a - 1, b, next, s);
				this.update(grid, a, b + 1, next, s);
				this.update(grid, a, b - 1, next, s);
				this.update(grid, a + 1, b + 1, next, s);
				this.update(grid, a - 1, b - 1, next, s);
				this.update(grid, a + 1, b - 1, next, s);
				this.update(grid, a - 1, b + 1, next, s);
				size--;
			}
		}
		return grid[x - 1][y - 1] == 0 ? -1 : grid[x - 1][y - 1];// 结尾被1环绕了
	}

	private void update(int[][] grid, int a, int b, int next, Queue<int[]> s) {
		if (a >= 0 && a < x && b >= 0 && b < y && (grid[a][b] == 0 || grid[a][b] > next)) {
			grid[a][b] = next;
			s.add(new int[] { a, b });
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
